﻿using System;
using System.Collections.Generic;
using STeaL.Functional;

namespace STeaL.Algorithm {
  public static partial class IListExtensions {
#region lower_bound
    public static int lower_bound<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred) {
      int count = last - first;
      while ( 0 < count ) {
        int count2 = count / 2;
        int mid = first + count2;
        if ( pred(list[mid], val) ) {
          first = ++mid;
          count -= count2 + 1;
        } else {
          count = count2;
        }
      }
      return first;
    }

    public static int lower_bound<T>(this IList<T> list, int first, int last, T val) where T : IComparable<T> {
      return lower_bound(list, first, last, val, rel_op.less<T>);
    }

    public static int lower_bound<T>(this IList<T> list, T val, Func<T,T,bool> pred) {
      return lower_bound(list, 0, list.Count, val, pred);
    }

    public static int lower_bound<T>(this IList<T> list, T val) where T : IComparable<T> {
      return lower_bound(list, 0, list.Count, val, rel_op.less<T>);
    }

#endregion
#region upper_bound
    public static int upper_bound<T>(this IList<T> list, int first, int last, T val, Func<T, T, bool> pred) {
      int count = last - first;
      while (0 < count) {
        int count2 = count / 2;
        int mid = first + count2;
        if (!pred(val,list[mid])) {
          first = ++mid;
          count -= count2 + 1;
        } else {
          count = count2;
        }
      }
      return first;
    }

    public static int upper_bound<T>(this IList<T> list, int first, int last, T val) where T : IComparable<T> {
      return upper_bound(list, first, last, val, rel_op.less<T>);
    }

    public static int upper_bound<T>(this IList<T> list, T val, Func<T, T, bool> pred) {
      return upper_bound(list, 0, list.Count, val, pred);
    }

    public static int upper_bound<T>(this IList<T> list, T val) where T : IComparable<T> {
      return upper_bound(list, 0, list.Count, val, rel_op.less<T>);
    }

#endregion
#region equal_range
    public static Tuple<int,int> equal_range<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred) {
      int count = last - first;
      while ( 0 < count ) {
        int count2 = count / 2;
        int mid = first + count2;
        if ( pred(list[mid], val) ) {
          first = ++mid;
          count -= count2 + 1;
        } else if ( pred(val, list[mid]) ) {
          count = count2;
        } else {
          return Tuple.Create(lower_bound(list,first,mid,val,pred), upper_bound(list,mid+1,first+count,val,pred));
        }
      }
      return Tuple.Create(first, first);
    }

    public static Tuple<int,int> equal_range<T>(this IList<T> list, int first, int last, T val) where T : IComparable<T> {
      return equal_range(list, first, last, val, rel_op.less<T>);
    }

    public static Tuple<int,int> equal_range<T>(this IList<T> list, T val, Func<T,T,bool> pred) {
      return equal_range(list, 0, list.Count, val, pred);
    }
    
    public static Tuple<int,int> equal_range<T>(this IList<T> list, T val) where T : IComparable<T> {
      return equal_range(list, 0, list.Count, val, rel_op.less<T>);
    }
    
#endregion
#region binary_search
    public static bool binary_search<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred, out int index) {
      index = lower_bound(list, first, last, val, pred);
      return ( index != last && !pred(val, list[index]));
    }

    public static bool binary_search<T>(this IList<T> list, int first, int last, T val, out int index) where T : IComparable<T> {
      return binary_search(list, first, last, val, rel_op.less<T>, out index);
    }

    public static bool binary_search<T>(this IList<T> list, T val, Func<T,T,bool> pred, out int index) {
      return binary_search(list, 0, list.Count, val, pred, out index);
    }

    public static bool binary_search<T>(this IList<T> list, T val, out int index) where T : IComparable<T> {
      return binary_search(list, 0, list.Count, val, rel_op.less<T>, out index);
    }

    public static bool binary_search<T>(this IList<T> list, int first, int last, T val, Func<T,T,bool> pred) {
      first = lower_bound(list, first, last, val, pred);
      return ( first != last && !pred(val, list[first]));
    }

    public static bool binary_search<T>(this IList<T> list, int first, int last, T val) where T : IComparable<T> {
      return binary_search(list, first, last, val, rel_op.less<T>);
    }

    public static bool binary_search<T>(this IList<T> list, T val, Func<T,T,bool> pred) {
      return binary_search(list, 0, list.Count, val, pred);
    }

    public static bool binary_search<T>(this IList<T> list, T val) where T : IComparable<T> {
      return binary_search(list, 0, list.Count, val, rel_op.less<T>);
    }

#endregion
  }
}
